/**
 * https://leetcode.cn/problems/generate-binary-strings-without-adjacent-zeros/submissions/?envType=daily-question&envId=2024-10-29
 */

class Solution {
public:
    vector<string> vt;
    string s;
    int h;
    bool k;
    void dfs(int n){
        if(n==h){
            vt.push_back(s);
            return;
        }
        if(!k){
            s+=48;
            k=true;
            dfs(n+1);
            s.erase(n,1);
        }
        s+=49;
        k=false;
        dfs(n+1);
        s.erase(n,1);
    }
    vector<string> validStrings(int n) {
        h=n;
        dfs(0);
        return vt;
    }
};